The present invention relates to a data management technology, and more particularly to an effective technology applied for management of plural pieces of data for an index key.
Recently, with the strong propagation of work systems operable through Internet, applications of database management systems (DBMS) supporting the systems are proceeding on a widening front. In this connection, the amount of data processed by the DBMS is increasing year by year. In the systems, a number of applications use a B-tree index which is a typical and the highest-speed retrieval means for the DBMS on the data having a narrow range of values such as xe2x80x98work transition statexe2x80x99, etc. in a work flow. Thus, the stable performance of the B-tree index becomes very important.
The B-tree index is disclosed by, for example, the document (Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers, 1993) basically about the data structure, the concurrent accessing method from a plurality of processes, and the basic system for recovery.
To realize a high-speed B-tree index as a practical system, the following problems have to be solved.
(i) Improving the Concurrent Executability of Plural Processes
A problem occurs when a plurality of transactions simultaneously access a database table containing records. Practically, when a transaction tries to update a record, and when another transaction simultaneously tries to access the same record, a conflict occurs. One of the solutions to the conflict is a locking system (exclusive access system) for a portion (the entire B-tree index, a node, an index entry, a key value, etc.) of a record or a B-tree index. In the locking system, a transaction is forced to obtain a lock before accessing data. If a lock has already been obtained by another transaction, there arises a conflict for a lock, and a necessary lock may not be obtained. Although the locking system guarantees an update result and a reference result of the current transaction, it keeps the access of a transaction waiting until another transaction which has previously obtained a lock releases the lock. Therefore, it is important to minimize the number of locks simultaneously obtained by one transaction and the range (granularity) of the influence of the lock to improve the multiplicity (concurrency) of the system and throughput.
(ii) Recovery Process Control
In an actual system, it is necessary to guarantee the atomicity of a transaction, and the consistency of the data in the B-tree index in case of various failures such as an interruption of a transaction, a system failure, a medium failure, etc. To attain this, a log record obtaining system and recovery process control using a log record are important. A log record obtaining system can be a physical log system in which a physical image before and after an update of the node forming an index is obtained according to log record information. In the recovery process performed using a physical image, access to a page for other transaction is limited until a transaction completes update. That is, the recovery process control closely relates to exclusive control, and also affects concurrent executability.
FIG. 11 shows a structure of a conventional typical B-tree index.
A B-tree index can be set such that a number of nodes at various levels are branched from a root node. An end node in the branched nodes is referred to as a leaf node. Nodes other than the leaf node including the root node are referred to as upper nodes. Each node has a plurality of index entries each comprising the following information. An index entry in a leaf node is configured by a pointer to a record (table data) in a database, and a key value indicating one of the features of the record (table data). An index entry in an upper node is configured by a pointer to a node (child node) at a level immediately below, and a key value indicating the range of the key value managed finally by the leaf node branched from the child node. The key value in an upper index entry functions as a sign (determination element) when an access program to a B-tree index traces the path from the root node to the leaf node in which an index entry containing a pointer to a target record is stored and managed. Normally, a node in a B-tree index is realized by a page as an access unit in a database.
One of the exclusive control systems for a B-tree index can be a key value exclusive system or a key range exclusive system using the granularity of the exclusive resources of an index as a xe2x80x98keyxe2x80x99. When the exclusive control of an index key is performed, the retrieving and updating process on the data (rows) having the same key are serialized by index key exclusive control, thereby lowering the concurrency. A transaction processed in a WEB environment which has recently been more and more popular is larger than a transaction of a conventional OLTP, and it is difficult to provide a high-throughput service in an exclusive control system on a key.
As shown in FIG. 11, there are the following problems with the B-tree index having a number of same keys. In the B-tree index shown in FIG. 11, table data information relating a key is managed by one leaf entry 16. The leaf entry 16 includes a key 14, table data information 18 (data record identifier) relating to the key value, and a number 17 (number of duplication) of pieces of table data information 18 relating to the key value. The table data information 18 is arranged in an ascending order in a list form of duplication. In this storage system, when the number of duplication of a key increases, the length of a leaf entry cannot be stored in a leaf node 12. As a result, the table data information for one key has to be divided into a plurality of leaf entries, and stored in a plurality of nodes. In the example shown in FIG. 11, the entries of the keys xe2x80x9828xe2x80x99 are stored separately in three nodes, that is, leaf nodes N4, N5, and N6. In this structure, the entries of the keys xe2x80x9828xe2x80x99 are bottlenecks in scanning leaf nodes using a pointer in the horizontal direction corresponding to the range search. Furthermore, the key 14 contained in an upper node 13 stored in the root node 10 and the upper node 13 has also to be a key in the table data information in addition to xe2x80x9828xe2x80x99, thereby causing the problem that the number of a root node 10 and the upper node 13 increases. As a result, a duplicate key lowers not only the performance of the access process on a duplication key itself, but also the access performance of the entire B-tree index, and the storage efficiency.
Gray discloses a method of managing table data information with the data structure other than the B-tree index, but does not disclose a method for concurrent execution control and recovery control. Furthermore, a recovery process system using a physical log is disclosed, but the above mentioned concurrent execution cannot be realized on the same page. These problems normally occur when index access is tried on the same key.
The object of the present invention is to solve the above mentioned problems, and provide a technology of performing index access on the same key in an environment where a plurality of access processing operations are performed.
The above mentioned problems are solved by the following means.
The problems are solved in an environment where a plurality of users gain access, and in a method for managing a B-tree index having a number of the same keys, with the data structure with which a plurality of data pointers relating to a key are stored, which is different from that of the leaf node storing an index entry containing the key, and in which data can be pointed to from an index entry containing the key to realize concurrent access in a plurality of processes. When a data pointer relating to a key is added or deleted, the first log record containing the information about adding or deleting the data pointer to or from the data structure storing the plurality of data pointers relating to the key is obtained, an index entry containing the key stored in a leaf node is updated, the second log record containing the information that the data pointer has been added or deleted to or from the data structure is obtained, and the data pointer is added or deleted to or from the data structure.